package solution

import (
	"fmt"
)

// 70. 爬楼梯

func Leecode70_climbStair(n int) int {
	if n == 1 {
		return 1
	}
	if n == 2 {
		return 2
	}
	return Leecode70_climbStair(n-1) + Leecode70_climbStair(n-2)
}


// 73. 矩阵置零
func Leecode73_setZeroes(matrix [][]int) {
	col, row := 0, 0
	// 当 m,n <= 64, 大于64？
	m, n := len(matrix), len(matrix[0])
	for i:=0; i<m; i++ {
		for j:=0; j<n; j++ {
			if matrix[i][j] == 0 {
				row |= 1 << i
				col |= 1 << j
				//fmt.Println(i, j, row, col)
			}
		}
	}
	for i:=0; i<m; i++ {
		if row & (1<<i) > 0 {
			for j:=0; j<n; j++ {
				matrix[i][j] = 0
			}
		}
	}
	for i:=0; i<n; i++ {
		if col & (1<<i) > 0 {
			for j:=0; j<m; j++ {
				matrix[j][i] = 0
			}
		}
	}
	fmt.Println(matrix)
	//fmt.Println(row, col)
}

// 74. 搜索二维矩阵
// from: https://leecode-cn.com/problems/search-a-2d-matrix

func Leecode74_searchMatrix(matrix [][]int, target int) bool {
	// 二分查找
	m, n := len(matrix), len(matrix[0])
	size := m * n
	left, right := 0, size-1
	for left <= right {
		i := (left + right)/2
		v := matrix[i/n][i%n]
		if target == v {
			fmt.Println("idx:", i/n, i%n)
			return true
		} else if target < v {
			right = i-1
		} else {
			left = i+1
		}
	}
	//fmt.Println(left, right)
	return false
}

// 75. 颜色分类
// from: https://leecode-cn.com/problems/sort-colors

func Leecode75_sortColor(nums []int) {
	var sort func(k *int, color, idx int)
	sort = func(k *int, color, idx int) {
		if idx >= len(nums) {
			return
		}
		if nums[*k] == color {
			*k = *k+1
		}
		if nums[idx] == color {
			nums[*k], nums[idx] = nums[idx], nums[*k]
			*k = *k+1
		}
		sort(k, color, idx+1)
	}
	k := 0
	sort(&k, 0, 1)
	sort(&k, 1, k+1)
	sort(&k, 2, k+1)
	fmt.Println(nums)
}

// 77. 组合
// from: https://leecode-cn/problems/combinations
// 回溯 + 剪枝
func Leecode77_combine(n int, k int) [][]int {
	//check := make([]bool, n)
	var ans []int
	var result [][]int
	var combine func(start int)
	combine = func(start int) {
		if k == len(ans) {
			res := make([]int, len(ans))
			copy(res[:], ans[:])
			result = append(result, res)
			return
		}
		for i:=start; i<n; i++ {
			ans = append(ans, i+1)
			combine(i+1)
			ans = ans[:len(ans)-1]
		}
	}
	combine(0)
	fmt.Println(result)
	return result
}

// 78. 子集
// from:

func Leecode78_subset(nums []int) [][]int {
	var result [][]int
	var ans []int
	var backtrack func(start int)
	backtrack = func(start int) {
		tmp := make([]int, len(ans))
		copy(tmp, ans)
		result = append(result, tmp)
		for i:=start; i<len(nums); i++ {
			if i>start && nums[i] == nums[i-1] {
				continue
			}
			ans = append(ans, nums[i])
			backtrack(start+1)
			ans = ans[:len(ans)-1]
		}
	}
	backtrack(0)
	fmt.Println(result)
	return result
}

// 79. 单词搜索

func Leecode79_exist(broad [][]byte, word string) bool {
	m, n := len(broad), len(broad[0])
	var dfs func(start, row int, direction int)
	dfs = func(start, row int, direction int) {
		for i:=0; i<n; i++ {
			if broad[row][i] == word[0] {
				continue
			}
		}
	}
	_ = m
	dfs(0, 0, 1)
	// TODO
	return true
}